# Least Recently Used
#
# Copyright (C) 2010 Yotam Medini <yotam.medini@gmail.com>
#
# This file is part of Gupicasa.
#
# Gupicasa is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# Gupicasa is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Gupicasa.  If not, see <http://www.gnu.org/licenses/>.


import arith


class Node:


    def __init__(self, data=None, prev_key=None, next_key=None):
        self.data = data
        self.prev_key = prev_key
        self.next_key = next_key


    def __str__(self):
        return "{%s, [<=]%s, [>=]=%s}" % (
            self.data, self.prev_key, self.next_key)


class Cache:


    def __init__(self, maxsize=0x10):
        self.d = {}
        self.maxsize = maxsize
        self.lru_head_key = None
        self.lru_tail_key = None
        self.queries = 0
        self.misses = 0


    def get(self, key):
        # sys.stderr.write("Cache.get(wh_from=%s)\n" % wh_from)
        self.queries += 1
        ret = None
        node = self.d.get(key, None)
        if node is None:
            self.misses += 1
        else:
            ret = node.data
            if self.lru_head_key != key:
                # move to head
                if self.lru_tail_key == key:
                    self.lru_tail_key = node.prev_key
                if node.prev_key is not None:
                    self.d[node.prev_key].next_key = node.next_key
                if node.next_key is not None:
                    self.d[node.next_key].prev_key = node.prev_key
                node.next_key = self.lru_head_key
                if self.lru_head_key is not None:
                    self.d[self.lru_head_key].prev_key = key
                node.prev_key = None
                self.lru_head_key = key
        # self.dump("After get")
        return ret


    def set(self, key, valua):
        # sys.stderr.write("Cache.set((<)%s, (>)=%s)\n" % (wh_from, wh_to))
        self.d[key] = Node(data=valua, next_key=self.lru_head_key)
        if self.lru_head_key is not None:
            self.d[self.lru_head_key].prev_key = key
        self.lru_head_key = key
        if self.lru_tail_key is None:
            self.lru_tail_key = key
        if len(self.d) > self.maxsize:
            old_node = self.d.pop(self.lru_tail_key)
            if old_node.prev_key is not None:
                self.d[old_node.prev_key].next_key = None
            self.lru_tail_key = old_node.prev_key
            del old_node.data
        # self.dump("After set")


    def dump(self, f, msg=None):
        if msg is not None:
            f.write("%s\n" % msg)
        f.write("map: {\n")
        for kv in self.d.items():
            f.write("[%s] -> %s\n" % kv)
        f.write("} list: {\n")
        k = self.lru_head_key
        while k is not None:
            node = self.d[k]
            f.write(" [%s] -> %s\n" % (k, node))
            k = node.next_key
        f.write("}\n")


if __name__ == '__main__':
    import random
    import sys
    import string

    opt = sys.argv[1]
    if opt == 'testcache':
        random.seed(0)
        maxsize = int(sys.argv[2])
        key_range = int(sys.argv[3])
        sample = int(sys.argv[4])
        sys.stdout.write("maxsize=%d, key_range=%d, sample=%d\n" %
                         (maxsize, key_range, sample))
        cache = Cache(maxsize)
        i = 0
        while i < sample:
            key = random.randrange(0, key_range)
            v = cache.get(key)
            if v is None:
                cache.set(key, 100*key)
            elif v != 100*key:
                sys.stderr.write("Unexpected: key=%d, v=%d\n" % (key, v))
                sys.exit(1)
            i += 1
        sys.stdout.write("Cache: size=%d, queries=%d, misses=%d\n" %
                         (len(cache.d), cache.queries, cache.misses))
        cache.dump(sys.stdout)

        sys.exit(0)

    else:
        sys.stderr.write("Unknown test\n")
        sys.exit(1)
